package list;

/**
 * 24. 两两交换链表中的节点
 *
 * @author Api
 * @date 2023/10/10 21:44
 */
public class Code24_SwitchingNode {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
            this.next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null && cur.next.next != null){
            ListNode temp = cur.next;
            ListNode temp1 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp;
            temp.next = temp1;
            cur = cur.next.next;
        }
        return dummyHead.next;
    }



    //
    public ListNode swapPairs2(ListNode head) {
        ListNode dummyHead = new ListNode(-1); // 设置一个虚拟头节点
        dummyHead.next = head; // 将虚拟头节点指向head,这样方便后面做删除操作
        ListNode cur = dummyHead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode fistNode; // 临时节点，保存两个节点中的第一个节点
        ListNode secondNode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            fistNode = cur.next;
            secondNode = cur.next.next;
            cur.next = secondNode; // 步骤一
            secondNode.next = fistNode; // 步骤二
            fistNode.next = temp; // 步骤三
            cur = fistNode; // cur移动，准备下一轮交换
        }
        return dummyHead.next;
    }

    // 递归版本
    public ListNode swapPairs1(ListNode head){
        // base case退出提交
        if (head == null || head.next == null){
            return head;
        }
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs1(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }
}
